package leetcode_回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * 括号生成
 * 算法：回溯
 *
 * @author yezh
 * @date 2024/3/4 17:22
 */
public class _22 {

    List<String> ans;

    public List<String> generateParenthesis(int n) {
        ans = new ArrayList<>();
        dfs(new StringBuilder(), 0, 0, n);
        return ans;
    }

    void dfs(StringBuilder cur, int left, int right, int n) {
        if (cur.length() == 2 * n) {
            ans.add(cur.toString());
            return;
        }
        if (left < n) {
            cur.append('(');
            dfs(cur, left + 1, right, n);
            cur.deleteCharAt(cur.length() - 1);
        }
        // 右括号的数量必须小于左括号
        if (right < left) {
            cur.append(')');
            dfs(cur, left, right + 1, n);
            cur.deleteCharAt(cur.length() - 1);
        }
    }

}
